//package acm.集美大学;
//
//import java.util.*;
//
//public class 工程师贝贝 {
//
//    static int n,m,q;
//    static List<Edge>[] nodes;
//    public static void main(String[] args) {
//        Scanner sc=new Scanner(System.in);
//        n = sc.nextInt();
//        m = sc.nextInt();
//        q = sc.nextInt();
//        nodes=new List[n+1];
//        for (int i = 1; i < nodes.length; i++) {
//            nodes[i]=new ArrayList<>();
//        }
//        for (int i = 0; i < m; i++) {
//            int u = sc.nextInt();
//            int v = sc.nextInt();
//            int w = sc.nextInt();
//            nodes[u].add(new Edge(u,v,w));
//            nodes[v].add(new Edge(v,u,w));
//        }
//        for (int i = 0; i < q; i++) {
//            int s = sc.nextInt();
//            int e = sc.nextInt();
//            int dis=dj(s,e);
//            System.out.println(dis);
//        }
//    }
//
//    public static int dj(int s,int e){
//        int[] dis=new int[n+1];
//        boolean[] vis=new boolean[n+1];
//        Arrays.fill(dis,Integer.MAX_VALUE);
//        PriorityQueue<int[]> queue=new PriorityQueue<>((a,b)->a[1]-b[1]);
//        queue.add(new int[]{s,0});
//        dis[s]=0;
//        int cnt=0;
//        while (!queue.isEmpty() && cnt < n) {
//            int[] poll = queue.poll();
//            int id = poll[0];
//            if (id==e) break;
//            if (vis[id]) continue;
//            int cur = poll[1];
//            cnt++;
//            vis[id]=true;
//            for (Edge edge : nodes[id]) {
//                int d=edge.w+cur;
//                if (dis[edge.to]>d){
//                    dis[edge.to]=d;
//                    queue.add(new int[]{edge.to,d});
//                }
//            }
//        }
//        return dis[e];
//    }
//
//    static class Edge{
//        int from,to,w;
//
//        public Edge(int from, int to, int w) {
//            this.from = from;
//            this.to = to;
//            this.w = w;
//        }
//    }
//}
